// threadtest.cc 
//	Simple test case for the threads assignment.
//
//	Create two threads, and have them context switch
//	back and forth between themselves by calling Thread::Yield, 
//	to illustratethe inner workings of the thread system.
//
// Copyright (c) 1992-1993 The Regents of the University of California.
// All rights reserved.  See copyright.h for copyright notice and limitation 
// of liability and disclaimer of warranty provisions.

#include "copyright.h"
#include "system.h"
#if defined(CHANGED) && defined(THREADS)
#include "synch.h"
#if defined(HW1_ELEVATOR)
#include "synchlist.h"

//----------------------------------------------------------------------
// ElevatorObj
//	The following class defines an "Elevator". An elevator 
// represented as a thread. It is controllered by using semaphores 
// or condition variables.]
// 	It simulates some people, also represented by threads, use the
// elevator from A floor to B floor(A and B can be the same floor in 
// this elevator).
//----------------------------------------------------------------------
class ElevatorObj {
public:
	ElevatorObj(int numFloor);// initialize an elevator
	virtual ~ElevatorObj();// Deallocate elevator
	void RequestAndWait(int atFloor);// recieve calling from a person
	void Enter(int toFloor);// A person enter the elevator 
				   //	and choose the floor to go.
	void Exit();	// A person go out of the elevator
	void Run();	// Starts the elevator
private:
	void AddToRoute(int floor);	//Sets a request to the controller for the elevator
	int currentFloor;	//Records the floor where the elevator is.
	SynchList* currentRoute;// A list records floor to go for the elevator 
				   // in running direction
	SynchList* nextRoute;// A list records floor to go for the elevator 
				   // in negative direction
	int* personCount;	//Records total number of people and the state of the elevator
	Lock* lock;	//Realize the semaphore
	Condition* eleCondition;//Records elevator stops or runs
	Condition* perCondition;//Records person takes action or waits for elevator
};
ElevatorObj* elevator;	//Creates a elevator
int num=0;
int out = 0;
#endif
#endif
// testnum is set in main.cc
int testnum = 1;
#if defined(CHANGED) && defined(THREADS)
int SharedVariable;
Barrier* barrier;
#ifdef HW1_SEMAPHORES
Semaphore sema("SimpleThread semaphore",1);
#endif
#ifdef HW1_LOCKS
Lock lock("SimpleThread lock");
#endif
void SimpleThread(int which) {
	int num, val;
	for(num = 0; num < 5; num++) {
#ifdef HW1_SEMAPHORES
		sema.P();
#endif
#ifdef HW1_LOCKS
		lock.Acquire();
#endif
		val = SharedVariable;
		printf("*** thread %d sees value %d\n", which, val);
		currentThread->Yield();
		SharedVariable = val+1;
#ifdef HW1_SEMAPHORES
		sema.V();
#endif
#ifdef HW1_LOCKS
		lock.Release();
#endif
		currentThread->Yield();
	}
#if defined(HW1_SEMAPHORES) || defined(HW1_LOCKS)
	barrier->wait();
#endif
	val = SharedVariable;
	printf("Thread %d sees final value %d\n", which, val);
}
#else
//----------------------------------------------------------------------
// SimpleThread
// 	Loop 5 times, yielding the CPU to another ready thread 
//	each iteration.
//
//	"which" is simply a number identifying the thread, for debugging
//	purposes.
//----------------------------------------------------------------------

void SimpleThread(int which) {
	int num;

	for (num = 0; num < 5; num++) {
		printf("*** thread %d looped %d times\n", which, num);
		currentThread->Yield();
	}
}
#endif
//----------------------------------------------------------------------
// ThreadTest1
// 	Set up a ping-pong between two threads, by forking a thread 
//	to call SimpleThread, and then calling SimpleThread ourselves.
//----------------------------------------------------------------------

void ThreadTest1() {
	DEBUG('t', "Entering ThreadTest1");

	Thread *t = new Thread("forked thread");

	t->Fork(SimpleThread, 1);
	SimpleThread(0);
}
#if defined(CHANGED) && defined(THREADS)
void
ThreadTestN(int n) {
	DEBUG('t',"Entering ThreadTestN");
	if(n < 0) {
		printf("n must be 0 or positive!");
		return;
	}
	barrier = new Barrier(n+1);
	for(int i = 0; i < n;i++) {
		Thread *t = new Thread("forked thread");
		t->Fork(SimpleThread,i+1);
	}
	SimpleThread(0);
}
//----------------------------------------------------------------------
// ThreadTest
// 	Invoke a test routine.
//----------------------------------------------------------------------

void ThreadTest(int n) {
	DEBUG('t',"Entering ThreadTest n number version");
	ThreadTestN(n);
}
#endif
//----------------------------------------------------------------------
// ThreadTest
// 	Invoke a test routine.
//----------------------------------------------------------------------

void ThreadTest() {
	switch (testnum) {
	case 1:
		ThreadTest1();
		break;
	default:
		printf("No test specified.\n");
		break;
	}
}
#if defined(THREADS) && defined(CHANGED) &&defined(HW1_LOCKS) &&defined(HW1_ELEVATOR)
//----------------------------------------------------------------------
// RunElevator
// 	Starts the elevator.
//----------------------------------------------------------------------
void RunElevator(int){
elevator->Run();
}
//----------------------------------------------------------------------
// Elevator
//	This call starts the elevator thread that serves numFloor floors.
// You can expect that the function is only called once and that
// the argument is greater than zero.
//	Floors are numbered starting from 1 to the maximum number of floors
// as defined by numFloors.
//
//	"numFloors" is an int value stored the number of floors
//----------------------------------------------------------------------
void Elevator(int numFloors) {
	elevator = new ElevatorObj(numFloors);
	Thread* t  = new Thread("Elevator");
	t->Fork(RunElevator,0);
}
//----------------------------------------------------------------------
// RunPerson
//	Simulates a person action and prints his behaviour.
//
//	"infoPtr" is an int value stored person id, "atFloor" and
// "toFloor".
//----------------------------------------------------------------------
void RunPerson(int infoPtr) {
	int* info = (int *)infoPtr;
	printf("Person %d wants to go to floor %d from floor %d. \n", info[0],
			info[2], info[1]);
	elevator->RequestAndWait(info[1]);
	printf("Person %d got into the elevator. \n", info[0]);
	elevator->Enter(info[2]);
	printf("Person %d got out of the elevator. \n", info[0]);
	elevator->Exit();
	delete info;
#ifdef ELEVATOR_TEST
	printf("%d persons used the elevator. \nAnd %d persons reached their destination.\n", num,out);
	printf("The elevator operated normally.\n ");
#endif
}
//----------------------------------------------------------------------
// FromTo
// 	This creates a student/faculty thread. It wakes up the elevator
// (when it is not already active), tells it the current floor
// the person is on, and waits until the elevator arrives. 
//	When the elevator arrives, it tells it which floor to go to.
// The elevator is amazingly fast, but it is not instantaneous 
// - it takes 100 ticks to go from one floor to the next.
//	There's only one elevator and more than one person (there is no
// upper limit ) can be in the elevator at a time. The trivial solution
// of serving one person at a time and putting others on hold is not
// acceptable. 
//
//	"atFloor" is an int value stored which floor a person requests.
// 	"toFloor" is an int value stored which floor a person wants to go.
//----------------------------------------------------------------------
void FromTo(int atFloor, int toFloor) {
	num++;
	int* info = new int[3];
	info[0] = num;
	info[1] = atFloor;
	info[2] = toFloor;
	Thread* t = new Thread("Person");
	t->Fork(RunPerson, (int)info);
}
//----------------------------------------------------------------------
// ElevatorObj::RequestAndWait
// 	Initialize an elevator
//----------------------------------------------------------------------
ElevatorObj::ElevatorObj(int numFloor) {
	currentFloor = 1;	//Set first floor as the initial floor where
				// the elevator is
	personCount = new int[numFloor + 1];	//personCount[0] is used  
							// to store the state 
							// (stop/run) of the elevator.
	for (int i = 1; i <= numFloor; i++) {
		personCount[i] = 0;
	}
	lock = new Lock("");
	currentRoute = new SynchList();
	nextRoute = new SynchList();
	eleCondition = new Condition("1");
	perCondition = new Condition("2");
}
//----------------------------------------------------------------------
// ElevatorObj::RequestAndWait
// Deallocate elevator
//----------------------------------------------------------------------
ElevatorObj::~ElevatorObj() {
	delete personCount;
	delete lock;
	delete eleCondition;
	delete perCondition;
	delete currentRoute;
	delete nextRoute;
}
//----------------------------------------------------------------------
// ElevatorObj::RequestAndWait
// 	Simulates the elevator recieves a calling from a person at some
// floor.
// 	If the elevator is not at the floor, the person needs to wait 
// and requests the elevator. If not, the person enter the elevator
// directly.
//
//	"aoFloor" is an int value recorded the floor a person requests 
//----------------------------------------------------------------------
void ElevatorObj::RequestAndWait(int atFloor) {
	lock->Acquire();
	if (currentFloor == atFloor&&personCount[0] == 0) {//Enter the
								   // elevator 
								   // directly.
		personCount[atFloor]++;
		lock->Release();
		return;
	}
	AddToRoute(atFloor);// Sets the floor the elevator needs to go
	while (currentFloor != atFloor || personCount[0] == 1)
		perCondition->Wait(lock);// Waits until the elevator
					    // is at the floor.
	lock->Release();
}
//----------------------------------------------------------------------
// ElevatorObj::Enter
// 	Simulates a person enter the elevator and choose the floor to go.
//
//	"toFloor" is an int value recorded the floor a person wants to go
//----------------------------------------------------------------------
void ElevatorObj::Enter(int toFloor) {
	lock->Acquire();
	AddToRoute(toFloor);// Sets the floor the elevator needs to go
	personCount[currentFloor]--;// Deletes the request number
	if (personCount[currentFloor] == 0){
		eleCondition->Signal(lock);}//Tells the elevator can move
	while (currentFloor != toFloor||personCount[0] == 1)
			perCondition->Wait(lock);// Waits until the elevator
						    // is at the floor.
	lock->Release();
}
//----------------------------------------------------------------------
// ElevatorObj::Exit
// 	Simulates a person go out of the elevator.
//
//----------------------------------------------------------------------
void ElevatorObj::Exit() {
	lock->Acquire();// enforce mutual exclusive access
	personCount[currentFloor]--;
	if (personCount[currentFloor] == 0)//Tells the elevator can move
		eleCondition->Signal(lock);
	lock->Release();
}
//----------------------------------------------------------------------
// ElevatorObj::AddToRoute
// 	Sets a request to the controller for the elevator. If the floor 
// to go is in running direction, adds it in the currentRote list. If
// not, adds it in the nextRoute.
//
//     "floor" is an int value stored which floor a person ask to use the
// elevator.
//----------------------------------------------------------------------
void ElevatorObj::AddToRoute(int floor) {
	if(!(lock->isHeldByCurrentThread()))
		lock->Acquire();	// enforce mutual exclusive access
	int* floorPtr = new int(floor);
	if (currentRoute->IsEmpty()) {//No requests and add request directly
		currentRoute->SortedInsert(floorPtr, floor);
		eleCondition->Signal(lock);//The lock must have been acquired
	} else {
		int * nextFloor = (int *) currentRoute->Top();//Shows next floor 
								    // the elevator to go.
		if(personCount[floor] == 0)		//If the floor is in the list, 
							// needn't be inserted.
		if (*nextFloor < currentFloor) {	//Sets when the elevator moves down.
			if (floor >= currentFloor) {
				nextRoute->SortedInsert(floorPtr, floor);
			} else {
				currentRoute->SortedInsert(floorPtr, -floor);
			}
		} else {	//Sets when the elevator moves up.
			if (floor <= currentFloor) {
				nextRoute->SortedInsert(floorPtr, -floor);
			} else {
				currentRoute->SortedInsert(floorPtr, floor);
			}
		}
	}
	personCount[floor]++;// Adds a person wants to use elevator on "floor" floor
	if(!(lock->isHeldByCurrentThread()))
		lock->Release();
}
//----------------------------------------------------------------------
// ElevatorObj::Run
// 	Move the elevator.
// There are two route list, one list is the current route, when current
// route is done, elevator will run the next route.
// When the elevator is moving, currentFloor !=nextFloor, and when it's
// stopped, currentFloor = nextFloor
//----------------------------------------------------------------------
void ElevatorObj::Run() {
	while (true) {
		lock->Acquire();
		if (currentRoute->IsEmpty()) {//No requests and no person in, wait
			eleCondition->Wait(lock);
			personCount[0] = 1;
		}
		lock->Release();
		while (!currentRoute->IsEmpty()) {//Have a floor to move to,
			//a person wants in or out
			for (int i = 0; i < 10000; i++) {//The procedure of moving
				currentThread->Yield();
			}
			lock->Acquire();
			int nextFloor = *((int *) currentRoute->Top());//Find next floor to move to
			if (currentFloor > nextFloor) {//Move down
				currentFloor--;
			} else if (currentFloor < nextFloor) {//Move up
				currentFloor++;
			}
			printf("Elevator arrives on floor %d.\n",currentFloor);
			if(currentFloor == nextFloor)//The destination
			{	personCount[0] = 0;
				perCondition->Broadcast(lock);//Let people out or in
				eleCondition->Wait(lock);//Wait till all people in and out
				int* temp_ptr = (int*)currentRoute->Remove();
						delete temp_ptr;
				personCount[0] = 1;
			}
			lock->Release();

		}
		lock->Acquire();
		//Current route is done,exchange the two list, go to next route.
		SynchList * temp = currentRoute;
		currentRoute = nextRoute;
		nextRoute = temp;
		lock->Release();
	}
}
#endif
